1. Field of Invention
The present invention relates generally to the field of quality-of-service (QoS) maintenance or enhancement over a data network. More specifically, the present invention is in one exemplary aspect directed to providing packets in a media stream with their own QoS and forward error correction (FEC) mechanism.
2. Description of Related Technology
So-called “Quality-of-service” or QoS refers generally to resource reservation and allocation control mechanisms. For example, QoS when implemented can provide different priority to different data flows, or guarantee a certain level of performance to a data flow. The goal of QoS is to improve the user experience and a network's ability to deliver predictable results for sensitive applications such as audio, video, and voice applications. Elements of network performance within the scope of QoS often include bandwidth (throughput), latency (delay), and error rate. There are generally two broad classes of QoS: data reliability and temporal reliability. Each makes different demands on network technologies.
QoS utilization and allocation of resources have long been implemented and described in the prior art for various other types of networks including, inter alia, packet switched networks. For example, U.S. Pat. No. 5,488,609 to Hluchyj, et al. issued Jan. 30, 1996 and entitled “Dynamic rate adjustment for overload control in communication networks” is exemplary of one such implementation. It discloses a device (500) and method (300) which provide for management of resource allocation on selected links in a connection-oriented communication network such that existing connections may share the burden of freeing up resources for accommodating new connections. The rate of certain connections is dynamically adjusted for the entire connection using information on the status of each link selected or marked for reallocation. Links are marked based on control information in the link state, and the in-call rate adjustment is based on negotiable Quality-of-service (QoS) parameters.
The current generation protocol standards for broadband access networks provide for a Quality-of-service (QoS) provisioning and forward error correction (FEC) provisioning of downlink data streams that is uniformly applied to all packets in a data stream. Examples of such networks include so-called “3G” (Third Generation) cellular and IEEE 802.11e networks. However, many multimedia streams, such as MPEG streams, contain a heterogeneous mix of packet types. Each type of packet within the stream can potentially be encoded differently according to media type (e.g. a different audio or video codec), and have its own QoS and/or error correction requirements. In addition, each type of packet can potentially be further differentiated according to frame type for a given codec. In some applications, QoS requirements and/or error correction requirements may change dynamically over the lifetime of the multimedia stream on the downlink. For example, FIG. 1 (prior art MPEG decoding) illustrates an MPEG video encoding 100 comprising three frame types, Intra frames 102 (I-frames), Predictive frames 104 (P-frames), and Bi-directional frames 106 (B-frames). I-frames are generally more important to an MPEG video codec than P-frames, and P-frames are generally more important to an MPEG video codec than B-frames. This is because P-frames are dependent on previous I-frames and P-frames, and B-frames are dependent on previous and future I-frames and P-frames. As a result, the loss of a B-frame will not affect I-frame and P-frame processing, yet the loss of a P-frame, though not affecting I-frame processing, may affect B-frame processing. Finally, the loss of an I-frame may affect both P-frame and B-frame processing.
One of the primary goals of video compression is to reduce the size (in bytes) of any particular video stream; MPEG compression thus aims to accomplish this reduction by removing spatial redundancy from within each video frame, and temporal redundancy between video frames. Such redundancy is known to occur frequently in video streams. For example, in a scene where a person moves in front of a stationary background, only the moving regions need to be represented. The parts of the scene that are not changing are redundant and therefore do not need to be transmitted repeatedly.
A variety of approaches are often used to minimize this redundancy, and therefore also minimize the information necessary for displaying the entire video stream. In some cases, data representing an entire image is required to be transmitted, while in other cases, the only data that is necessary is the data representing the differences between the current image and the prior one. Other approaches can also be utilized, such as techniques in global motion compensation, block motion compensation, variable block-size motion compensation, motion estimation, etc. Typically, the approach which requires the fewest bits for image representation is the approach which is deemed optimal for a particular instant in time. Since the optimal approach usually varies with time (and in many instances, may also depend upon what image was sent in the prior instant in time), then in these cases, a plurality of frame types is used in order to accomplish optimization of the video stream (for example, in an MPEG stream, the I-frame, B-frame, and P-frame formats discussed above).
FIG. 2 is a block diagram illustrating a generalized three node transmission stream sequence as known in the prior art. A media stream 202 is transmitted from an application server 206 to a base station 208; the base station transmits the media stream to the mobile station 210. As shown by the figure, the media stream comprises n data packets 200, 200(1)-200(n), where each data packet is assigned to one of i packet types 204, 204(1)-204(i). The sequencing of the transmitted packets need not necessarily correspond with any sequencing of possible packet types. For example, the first and second packets 200(1) 200(2) in the stream 202 might be a Type 1 packet 204(1), while the third packet 200(3) might be a Type 2 packet 204(2).
Irrespective of packet type 204, the access network or base station 208 selects an appropriate transmission mode for all data packets 200 in the media stream 202. This mode is selected based upon what is necessary for the transmitter 208 to accommodate the highest QoS necessary for any individual packet 200(1)-200(n) within the stream 202, to ensure timely delivery at the mobile station 210. The mode selected may potentially also select the most expansive error correction protocol necessary to reasonably accommodate the transmission of any individual packet 200(1)-200(n) within the media stream 202. In this manner, the mode selected may be chosen based upon any of the following aspects of a connection (or combination thereof): time to provide service, audio quality, video quality, echo, loss, reliability, and/or error correction. The mobile receiver 210 comprises any logic necessary for accommodating the transmission mode selected.
Traditionally, access networks 208 parse the “Type of Service” field in an IPv4 header, or the “Traffic Class field” in an IPv6 header to determine data handling processes. These field values are mapped by the access network to an internal QoS policy and/or error correction policy for delivery. For certain applications (e.g. MPEG data streams), various packets within a data stream require different QoS levels. Referring back to FIG. 1, a media stream comprised of I-frames 102, B-frames 106, and P-frames 104 is being transmitted by an access network. As previously mentioned, the base station selects an appropriate transmission mode for all data packets within the media stream. The transmitter operates on “physical” and “medium access control” layers, and must treat the media stream as a single unified data stream. The transmitter does not have sufficient computing resources to further classify packets by a combination of the application and its individual application-layer packet types (the transmitter does not have “application layer” processing capabilities). Even with sufficient resources to perform application layer classification, the transmitter cannot duplicate the decision logic within every application that dynamically chooses the correct QoS requirements for individual packet types. Due to the media stream's mixed composition of frames, the transmitting device must accommodate the highest level of both QoS and error correction (the I-frame is the most critical frame type for MPEG encoding/decoding, and will necessitate high QoS and error correction for the entire media stream).
Current and next generation access networks can perform deeper packet inspection than the aforementioned “Type of Service” fields in order to perform the packet classification required for QoS policy enforcement. Deeper packet inspection can allow packet classification of higher protocol layers in application streams with such classification mapped to specific QoS policies. However, as these solutions do not perform application-aware functionality (for aforementioned reasons), and require the access network to be programmed ahead of time with the proper QoS policy of every class of application stream that is supported by the access network. Supported application stream classes must be determined a-priori by a management system component of the access network and communicated to every base station in the access network. In this way, all application streams that are mapped to a particular stream class by a base station will have the same QoS policy enforced.
Since the access network cannot anticipate every possible application that might use the network to stream multimedia packets, it cannot rely upon packet classification to identify any and all future applications whose streams are transported over the access network. Instead, all possible classes of streams that are supported by the QoS policies are identified. Each application stream is thereby mapped to a particular stream class by the packet classification algorithm. As a result, a plurality of application streams might result in the same classification without the awareness of the base station.
As evidenced by this arrangement, the prior art relies upon a common logic in order to process each data packet 200(1)-200(n) arriving at the mobile station 210. The prior art is inefficient in the sense that certain packet types need not require the same error correction/quality-of-service provisioning necessary for other packets types. More specifically, the error correction/quality-of-service provisioning cannot change dynamically during the media stream session. Static provisioning for packet types of changing requirements often unnecessarily wastes high priority network resources on lower priority packet types, and increases the number of bytes necessary for transmitting the entire media stream 202 (and likewise, increases the media stream's 202 expected transfer time). At the other extreme, selecting a less stringent transmission mode for the media stream 202 in order to increase transfer speed results in lower priority network resources being used for high priority packet types, and unacceptable packet error rates. In the same vein, selecting an error correction protocol with less redundancy often requires retransmission of all or part of the media stream 202 in the event that errors ultimately occur. In some cases, the efficiency gains associated with the selection of an error correction protocol with less redundancy are more than offset by the efficiency costs of retransmission.
For example, an iTunes movie that is viewed on a client device as it is being streamed (let's say a user is watching a preview) may have a very different QoS requirement set for P-frames, B-frames, and I-frames, than an iTunes movie that is downloaded to the client device in the background for later viewing offline. For every variation in downlink QoS requirements demanded by the iTunes application, the access network would have to maintain a separate stream classification. This can become impractical for large numbers of applications with large numbers of stream types per application.
U.S. Pat. No. 7,085,291 to Zhang et al. filed on Aug. 1, 2006 discloses an enhanced radio link protocol (RLP) in a wireless access network that is network aware. The RLP attempts to increase radio link quality by various Automatic Repeat reQuest (ARQ) mechanisms. The RLP framing structure included supports and enables at least network layer packet boundary detection, dynamic and adaptive ARQ schemes for QoS support on a per-packet basis, and an RLP frame structure for fast adaptation to physical layer channel rate/RLP frame sizes. Optional uses include supporting negative acknowledgment (NAK) based ARQ.
U.S. Pat. No. 7,301,928 to Nakabayashi et al. filed on Nov. 27, 2007 discloses an error correction encoding rate selection table provided in an error correction processing unit of a packet transfer apparatus. The table stores an error correction encoding rate preset to maintain a desired QoS in correspondence with a protocol type and an application type. When a transmission packet is transferred to a wireless transmission path, an encoding control unit judges the protocol type and application type of a transmission packet from a header of the transmission packet, and in accordance with a judgment result and the error correction encoding rate selection table, an error correction encoding rate is selected, and the transmission packet is subjected to error correction encoding and transferred.
U.S. Pat. No. 7,075,927 to Mo et al. filed on Jul. 11, 2006 discloses a method and system for transporting traffic having disparate qualities of service classes across a packet-switched network that includes receiving at an ingress node of a network a plurality of packets, some of which comprise a transport label, where the transport label has an associated QoS class that is defined externally to the network. Packets having a QoS class comprising delay bound guarantees and a low drop priority are combined into a first internal QoS class. Packets having a QoS class comprising a flexible drop priority and no delay bound guarantees are combined into a second internal QoS class. Packets having a QoS class including no delivery guarantees are combined into a third internal QoS class. The packets are transmitted in the network based on their internal QoS class.
U.S. Pat. No. 7,016,366 to Kawarai et al. filed on Mar. 21, 2006 discloses a method to achieve QoS control, drop control and multicast control of a variable-length packet at high speed in small-scale hardware. A packet divider divides a variable-length packet into fixed-length packets, and an input buffer section stores the divided fixed-length packets into queues by output lines and by QoS classes. A large number of QoS classes are mapped into only two kinds of classes including a guaranteed bandwidth class for which an assigned bandwidth is guaranteed and a best effort class for which a surplus bandwidth is allocated, thereby to achieve scheduling at the input side by an inter-line scheduler. An output buffer section assembles a variable-length packet from fixed-length packets that have been obtained by switching at a switch section in an output buffer section. A QoS control is performed based on a packet length.
U.S. Pat. No. 7,263,064 to Yoshimura et al. filed on Aug. 28, 2007 discloses a method for transmitting packets classified according to QoS requirement from a transmitting node to a receiving node. The transmitting node is configured to select sequentially a QoS class, to divide a queued packet to be transmitted into a plurality of predetermined data units, to transmit one of the predetermined data units, and to apply a transmitter-side retransmission control process to the data unit to be transmitted when the selected class is a QoS class specified for data type packets. The receiving node is configured to receive sequentially the data units transmitted from the transmitting node, to assemble a plurality of received data units to restore an original packet for each QoS class, and to apply a receiver-side retransmission control process to the received data units when the received data unit belongs to one of the data type QoS classes.
U.S. Pat. No. 7,292,591 to Parker et al. filed on Nov. 6, 2007 discloses a packet processing system architecture and method. According to a first aspect of the invention, packet parser functions are distributed throughout a packet processing system comprising a packet classification system and a packet modification system. According to a second aspect of the invention, an egress mirroring function is provided to the system. According to a third aspect of this invention, a multi-dimensional quality-of-service indicator for a packet is provided. According to a fourth aspect of this invention, a cascaded combination of multiple, replicated packet processing systems is used to process a packet. A fifth aspect of this invention involves any combination of one or more of the foregoing.
U.S. Pat. No. 7,280,562 to Sindhushayana et al. filed on Oct. 9, 2007 discloses a method and apparatus for variable length Physical Layer packet generation. Multiple Security Layer packets may be multiplexed into a single Physical Layer packet to increase efficiency, wherein the Multiple Security Layer packets may have variable lengths. In one embodiment, different format Multiple Security Layer packets for different users are combined into capsules that form the Physical Layer packet. Shorter packets are for users in poor channel conditions or requiring smaller amounts of data due to the applications and the accompanying QoS requirements. In one embodiment, a modified Preamble structure provides for Unicast or multi-user packets. Alternate embodiment provides modified Rate Sets, a mechanism for identifying ACK from a single-user packet or a multiplexed packet (delayed ACK), ON/OFF keying for ACK channel v/s bi-polar keying used in IS-856, and/or multi-valued interpretation of DRC.
U.S. Pat. No. 7,180,860 to Fonden et al. filed on Feb. 20, 2007 discloses a method for the provision of a defined quality-of-service in a packet switched communication system with interconnected nodes for the forwarding of data packets is described. The system comprises at least one edge node for the connection to user equipment or a further communication system and for processing data packets. The packets comprise a data field specifying the handling of the packets and the nodes perform a differentiated handling of packets according to said data field. The communication system comprises or is connectable to a database which contains a record for a user specifying a quality-of-service. An edge node which processes a packet for said user is provided with quality parameters from the database. The edge node sets the data field specifying the handling of the packet according to the record. Devices and programs to perform the method are also described.
European Patent Publication No. EP1739900 to Lin entitled “A METHOD FOR ACQUIRING THE QOS OF THE MULTIMEDIA STREAM PERIODICALLY” discloses a method for acquiring media stream Quality of Service (QoS) periodically. The MGC sets an inspect duration during which the MGC periodically acquires the QoS information of the media stream, thereby acquiring the QoS information of the media stream and controlling the media stream. Two ways for the MGC periodically acquiring the QoS information are provided. The MG actively submits the QoS information to the MGC and the MG submits the QoS information to the MGC according to the periodic request of the MGC. One embodiment provides the capability of adjusting the call microscopic QoS, enhances the real-time quality of evaluating the QoS and that of dynamically adjusting call control strategy, inherits the ability of the original protocol for evaluating the microscopic QoS of the network during a certain period and ostensibly provides more accurate evaluation.
U.S. Pat. No. 7,068,645 to Phadnis et al. filed on Jun. 27, 2006 discloses a network device (for example, a network access server or home gateway) providing different quality-of-services to different layer-3 datagrams when transporting on tunnels. A tunnel may be implemented to provide different QoS to different packets depending on the packet header. The network device examines the header of each datagram to determine the specific QoS to be provided. At least the data portion in the datagram is encapsulated for transportation on the tunnel. The encapsulated data portion in turn is encapsulated in the form of one or more packets, with the packet format to reflect the QoS determined for the datagram. When the tunnel is implemented on UDP/IP and the datagram is an IP (Internet protocol) datagram, the TOS/Precedence bits of the IP datagram may be copied into the precedence/TOS bits of the UDP/IP packet(s).
U.S. Pat. No. 5,581,544 to Hamada, et al. issued Dec. 3, 1996 and entitled “Method and apparatus for evaluating in ATM multiplexing apparatus in which priority control is performed and for controlling call admissions and optimizing priority control on the basis of the evaluation” discloses a probability transition matrix St that expresses a multiplexing process which includes nested threshold priority control and classified priority control. A state equation using the matrix St is solved by substituting therein upper and lower bounds of a probability distribution of a cell arrival count at in an average time series, to calculate a probability distribution of a cell length in a buffer. From the thus calculated cell length probability distribution, the QoS is evaluated on a priority class basis. Based on the QoS evaluation, optimization of call admission control and priority control is accomplished.
U.S. Pat. No. 7,283,803 to Karaoguz, et al. issued Oct. 16, 2007 and entitled “Location-aware application based quality-of-service (QoS) via a broadband access gateway” discloses a system and method supporting access to multimedia information based upon user-defined quality-of-service criteria is disclosed. A broadband access gateway may coordinate network behavior during the transition of an access device among communication pathways having different available capacities. Adjustments in bitrates and levels of compression may be made based upon the user-defined quality-of-service criteria. The user may be notified when network conditions disallow support for the desired quality-of-service, and may choose to override selected criteria. The user-defined quality-of-service criteria may be stored within the gateway and associated with a user, or may be located in the access device and accessible to the gateway.
Finally, prior art methods are inefficient because each type of access network (e.g. Wi-Fi, LTE, or WiMAX) can potentially have its own unique set of QoS policy parameters. This means that each access network could translate the same packet into a slightly different access network QoS policy, having undesirable results as the mobile device roams from one access network to another.
Forward Error Correction (FEC)—
Forward error correction (FEC) is a system of error control and correction useful in digital data transmission. In a typical FEC implementation, the transmitter adds redundant data to its outgoing messages in the form of a systematic or non-systematic error correction code. This approach allows the receiver of the data (including the embedded or associated FEC data) to detect and correct errors without the need to ask the transmitter for additional data (such as via a retransmission). As the name implies, the error correction code enables the receiver to “reconstruct” the original data sequence by knowing how it was originally encoded at the transmitter. One advantage of forward error correction is that retransmission of data can often be avoided (thereby obviating associated higher bandwidth requirements). FEC is therefore particularly useful in situations where data retransmissions are expensive, cost-prohibitive, or even unavailable.
Two primary categories of FEC include block coding and convolutional coding. Block codes are applied to fixed-size blocks (packets) of bits or symbols of predetermined size. Convolutional codes are applied to a bit or symbol streams of arbitrary length. Numerous types of block codes exist, one of the most notable being Reed-Solomon coding. Reed-Solomon coding is widely used for example on compact discs, DVDs, and in computer hard drives (HDDs). Other types of block codes include Golay, BCH and Hamming codes, each of which are also well known in the art.
Convolutional codes are most often decoded with the Viterbi algorithm, though other algorithms are sometimes used. Convolutional codes are those which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n≧m) and (b) the transformation is a function of the last k information symbols, where k is the constraint length of the code. Convolutional codes may be recursive or non-recursive, and like block codes systematic or non-systematic as well.
Trellis codes are another form of convolutional code. The name “trellis” was coined because a state diagram of the technique, when drawn on paper closely resembles the trellis lattice used in a rose garden. The scheme is basically a convolutional code of rates (r, r+1).
Block and convolutional codes are sometimes combined in concatenated coding schemes in which the convolutional code and the block code (usually Reed-Solomon) cooperate to provide a synergistic effect.
Another type of channel error correction coding is the well known “turbo” code, a scheme that combines two or more relatively simple convolutional codes and an interleaver to produce a block code that can reach performance very close to that of the theoretical Shannon limit with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance. See, e.g., U.S. Pat. No. 5,446,747 to Berrou entitled “Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoder” issued Aug. 29, 1995 and incorporated herein by reference in its entirety.
Code “puncturing” is a technique used to make an m/n rate code from a “basic” rate ½ code. It is reached by deletion of some bits in the encoder output. Bits are deleted according to puncturing matrix. The specific order of transmission is defined by the respective communication standard. Punctured convolutional codes are widely used in satellite communications, for example, in digital video broadcasting (DVB).
Low-density parity-check (LDPC) codes are a class of linear block LDPC codes. Their name comes from the characteristic of their parity-check matrix which is said to be sparse (i.e., contains only a few 1's in comparison to the amount of 0's). The main advantage of LDPC codes is that they provide a very high level of performance (close to the Shannon limit) for many different channels and linear-time complex algorithms for decoding. Furthermore, they are suited for implementations that make heavy use of parallelism. Despite the foregoing wide range of approaches to implementing QoS policy and forward error correction (FEC) within digital communication systems, improved methods and apparatus for allowing each packet in a media stream to have its own quality-of-service and/or error correction requirements are needed. In this manner, efficiency gains during transmissions of data streams may be realized, since the transmission of redundant data bearing only a marginal utility would thereby be reduced and/or eliminated, yet without significantly increasing the likelihood of performing inefficient retransmissions of the data.
Such improved methods and apparatus would also ideally enable specific quality-of-service and/or error correction logic to apply to packets on an individual basis and set the priority for different types of data packets or frames; e.g., such as prioritizing I-frames over P-frames and P-frames over B-frames, etc.